class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for num in nums:
        	res ^= num
        return res


    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = nums[0]
        times = 1
        for num in nums[1:]:
        	if num != res:
        		if times == 0:
        			res = num
        			times = 1
        		else:
        			times -= 1
        	else:
        		times += 1
        return res

    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix:
        	return False
        
        xx = len(matrix) - 1
        yy = 0
       	
       	xlen = len(matrix)
       	ylen = len(matrix[0])
       	while 0 <= xx < xlen and 0 <= yy < ylen:
       		if matrix[xx][yy] == target:
       			return True
       		elif matrix[xx][yy] > target:
       			xx -= 1
       		else:
       			yy += 1
        return False

    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        l = m + n -1
        if l < 0:
        	return
        m -= 1
        n -= 1
        while m > -1 or n > -1:
        	if n < 0:
        		return
        	else:
        		if m < 0:
        			nums1[l] = nums2[n]
        			l -= 1
        			n -= 1
        		else:
        			if nums1[m] < nums2[n]:
        				nums1[l] = nums2[n]
        				n -= 1
        			else:
        				nums1[l]= nums1[m]
        				m -= 1
        			l -= 1




if __name__ == '__main__':
	matrix = [
			  [1,   4,  7, 11, 15],
			  [2,   5,  8, 12, 19],
			  [3,   6,  9, 16, 22],
			  [10, 13, 14, 17, 24],
			  [18, 21, 23, 26, 30]
			]
	aa = Solution()
	print aa.searchMatrix(matrix, 5)